#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void MD5(char *msg, size_t len, unsigned char *digest)
{
    typedef unsigned int u32;
    u32 h[] = {0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476};
    static const u32 k[64] =
    {
        0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
        0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
        0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
        0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
        0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
        0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
        0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
        0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
        0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
        0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
        0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
        0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
        0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
        0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
        0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
        0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
    };
    static const u32 qz[] =
    {
        7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
        5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20,
        4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
        6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21
    };
    static const u32 s[] =
    {
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
        1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12,
        5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2,
        0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9
    };
    u32 H[4], i, j, f, tmp, R;
    size_t n_len = ((len + 8) / 64) * 64 + 56;
    unsigned char *n_msg = (unsigned char *)malloc(n_len + 8);
    memset(n_msg, 0, n_len + 8);
    memcpy(n_msg, msg, len);
    n_msg[len] = 0x80;
    n_msg[n_len] = len * 8;
    for(j = 0; j < n_len; j += 64)
    {
        memcpy(H, h, 4 * sizeof(u32));
        for(i = 0; i < 64; i++)
        {
            switch(i / 16)
            {
	            case 0: f = (H[1] & H[2]) | ((~H[1]) & H[3]); break;
	            case 1: f = (H[3] & H[1]) | ((~H[3]) & H[2]); break;
	            case 2: f = H[1] ^ H[2] ^ H[3]; break;
	            case 3: f = H[2] ^ (H[1] | (~H[3]));  break;
            }
            tmp = H[3];
            H[3] = H[2];
            H[2] = H[1];
            R = H[0] + f + k[i] + ((u32 *)n_msg)[s[i] + j];
            H[1] = H[1] + ((R << qz[i]) | (R >> (32 - qz[i])));
            H[0] = tmp;
        }
        for(i = 0; i < 4; i++) h[i] += H[i];
    }
    free(n_msg);
    memcpy(digest, h, 16);
}

int main(int argc, char *argv[])
{
    int i;
    // e10adc3949ba59abbe56e057f20f883e
    char str[] = "123456\n";
    unsigned char result[16];
    MD5(str, strlen(str), result);
    for (i = 0; i < 16; i++)
        printf("%02x", result[i]);
    putchar('\n');
    return 0;
}

